package offer;

import java.util.ArrayList;
import java.util.List;

public class offer_0041 {
    class MedianFinder {
        int current;
        List<Integer> list;
        /** initialize your data structure here. */
        public MedianFinder() {
            current=0;
            list=new ArrayList<>(2000);
        }

        public void addNum(int num) {
            if(current!=0){
                if(num>=list.get(current-1)) list.add(num);
                else if(num<=list.get(0)) list.add(0,num);
                else {int index=search(list,0,current-1,num);
                list.add(index,num);}
            }
            else list.add(num);
            current++;
        }
        private int search(List<Integer> list,int left,int right,int num){
            if(right-left<=1) return right;
            int mid=(right-left)/2+left;
            if(list.get(mid)<num){
                return search(list,mid+1,right,num);
            }
            else return search(list,left,mid,num);
        }
        public double findMedian() {
            if(current%2==0) {
                int mid=(current-1)/2;
                return (list.get(mid)+list.get(mid+1))/2.0;
            }
            return list.get((current-1)/2);
        }
    }
}
